class Node {
  constructor(name, children) {
    this.name = name;
    this.children = children;
  }
}

var root = new Node("root", [
  new Node("A", [new Node("a1", []), new Node("a2", [])]),
  new Node("B", [new Node("b1", [])]),
  new Node("C", []),
]);

// console.log(root);

// BFS
const print = (root) => {
  var queue = []; //队列
  queue.unshift(root);
  while (queue.length != 0) {
    var item = queue.shift();
    console.log(item.name);
    for (let i = 0; i < item.children.length; i++) {
      queue.push(item.children[i]);
    }
  }
};

// DFS
const print_dfs = (root) => {
  var stack = [];
  stack.push(root);
  while (stack.length != 0) {
    var item = stack.pop();
    console.log(item.name);
    var children = item.children;
    for (var i = children.length - 1; i >= 0; i--) stack.push(children[i]);
  }
};

/**
 * DFS比BFS更有利于操作节点之间关系
 */

// DFS
const getFNode = (root, name) => {
  var f = root;
  var stack = [];
  stack.push(root);
  while (stack.length != 0) {
    var item = stack.pop();
    if (item.name == name) {
      return f;
    }
    var children = item.children;
    for (var i = children.length - 1; i >= 0; i--) stack.push(children[i]);

    // 非节点
    if (item.children.length > 0) {
      f = item;
    }
  }

  return null;
};

// DFS
const add = (root, name, newNode) => {
  var stack = [];
  stack.push(root);
  while (stack.length != 0) {
    var item = stack.pop();
    var children = item.children;
    for (var i = children.length - 1; i >= 0; i--) {
      if (children[i].name == name) {
        children.splice(i + 1, 0, newNode);
        return;
      }
      stack.push(children[i]);
    }

    console.log(item);
  }
};

// DFS
const del = (root, name) => {
  var stack = [];
  stack.push(root);
  while (stack.length != 0) {
    var item = stack.pop();
    var children = item.children;
    for (var i = children.length - 1; i >= 0; i--) {
      if (children[i].name == name) {
        children.splice(i, 1);
        return;
      }
      stack.push(children[i]);
    }
  }
};

add(root, "a2", new Node("a3", []));
// del(root, "a2");
print_dfs(root);
